package violentRecursion;

/**
 * @className: LeetCode_1143
 * @Description: 最长公共子序列
 * @author: kunkun
 * @date: 2025/5/17 11:28
 */
public class LeetCode_1143 {

    int res = 0;

    public int longestCommonSubsequence(String text1, String text2) {
        res = 0;
        solution_2(text1,text2,0,0,0);
        return res;
    }

    /**
     * @Author kunkun
     * @Description 暴力递归
     * @Date 11:38 2025/5/17
     **/
    private void solution_1(String str1, String str2, int i, int j, int size) {
        //1. 截止条件
        if (i==str1.length() || j==str2.length()){
            res = Math.max(res,size);
            return;
        }
        //2. 递归判断
        if (str1.charAt(i)==str2.charAt(j)){
            solution_1(str1,str2,i+1,j+1,size+1);
        }else{
            solution_1(str1,str2,i+1,j,size);
            solution_1(str1,str2,i,j+1,size);
        }
    }

    /**
     * @Author kunkun
     * @Description 动态规划
     * @Date 11:38 2025/5/17
     **/
    private void solution_2(String str1, String str2, int x, int y, int size) {
        //1. 定义变量
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        //2. 递归推导
        for (int i = str1.length()-1; i >=0 ; i--) {
            for (int j = str2.length()-1; j >=0 ; j--) {
                if (str1.charAt(i)==str2.charAt(j)){
                    dp[i][j]=dp[i+1][j+1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        res = dp[0][0];

    }


}
